The present invention relates to the field of computer networking. In particular the present invention discloses a method and apparatus for generating port addresses that can be used for implementing a very fast look-up method to be performed for high-speed address translation.
The Internet is a global interconnection of computer networks that share a set of well-defined data communication protocols. Specifically, most computer networks coupled to the global Internet communicate using the Transmission Control Protocol (TCP) and Internet Protocol (IP).
The Internet Protocol (under the current version 4) uses thirty-two bit numbers for addresses. The Internet Protocol addresses are usually written out in xe2x80x9cdotted decimalxe2x80x9d notation using a set of four numbers that are between zero (0) and two hundred fifty-five (255). The Internet Protocol addresses are allocated by an entity known as the Internet Assigned Numbers Authority (IANA) that maintains a web site at http://www.iana.org/.
Recently, a shortage of available Internet Protocol addresses has developed. The shortage has been caused by the exponential growth of the Internet in the last ten years and early inefficient IP address space allocation. There is now a scarcity of IP addresses such that new entities that wish to connect to the Internet either do not receive as many Internet addresses as they desire or are forced to pay a high price for additional IP address space.
In order to combat this problem, systems having network address translation were Created. Network address translation functions are typically built into routers or Internet firewalls. Network address translation is used to allow an entity with many internal computer nodes using xe2x80x9cillegalxe2x80x9d Internet protocol addresses to share one or more legally allocated Internet protocol addresses. Specifically, an internal network is created with a set of xe2x80x9cinternalxe2x80x9d Internet protocol addresses that are not allowed to be used on the Internet.
A typical device with network address translation has two different network ports. The two-port network address translation device has first port coupled to the internal network with an xe2x80x9cinternalxe2x80x9d network address. The second port of the two-port network address translation device is coupled to the global Internet with a legally allocated Internet protocol address. The two-port network address translation device handles all Internet communication from internal computer nodes coupled to the internal network.
The two-port network address translation device may perform a number of different functions such as packet filtering, protocol proxying, and split domain name service (DNS). However, one of the features that must be performed by the two-port network address translation device is a translation from internal network addresses into legal Internet addresses and vice versa. Specifically, when an internal network node attempts to communicate with a server on the Internet, the internal address is replaced with a legal Internet protocol address assigned to the two-port network address translation device. When the two-port network address translation device receives a response from the Internet server, the two-port network address translation device must translate the destination address of the response back into the internal address of the internal network node that initiated the communication. The translated packet is then passed on to the Internet network.
To perform Network Address Translation, the two-port network address translation device must maintain a list of all the active connections such that the two-port network address translation device knows which connections are assigned to which internal network bodes on the internal network. Most devices that perform network address translation use a simple list to store information about the current connections. Each time an internal network node uses an established connection or a response packet is received from the Internet server, the network address translation device must search the connection table to locate the internal network node that owns the connection. Searching the connection list takes time and thus introduces delays in the Internet communication. It would therefore be desirable to have a faster method of maintaining a list of connections.
The present invention discloses a method and apparatus for performing network address translation. The method of the present invention operates by generating statistically unique port numbers for outgoing connections that pass through a network address translation device. The statistically unique port numbers are formed from a subset of bits from the source node""s IP address and a subset of bits from the port number assigned by the source node. Information about each connection is stored in a table of connections. When a server responds to a newly initiated connection, the server will respond to the assigned statistically unique port number on the network translation device. The network translation device uses the statistically unique port number in the response packet to find information about the connection. Specifically, the statistically unique port number is transformed into an index into the table of connection information.
When the statistically unique port number fails to be absolutely unique, the present invention uses a secondary fallback system that generates an absolutely unique port number using another means. In one embodiment, the secondary fallback system assigns sequential numbers. The information about connections that use unique port numbers generated by the secondary system are stored in a secondary connection table. In one embodiment, the secondary connection table is organized using a Patricia tree format.
Other objects, features, and advantages of present invention will be apparent from the company drawings and from the following detailed description.